A variety of specialized software tools have been developed to meet the challenges of designing and manufacturing more complex and higher performance electronic systems such as printed circuit boards and integrated circuits (ICs). Layout verification software, such as layout-vs-schematic (LVS) and design rule check (DRC), is used to ensure that the layout connectivity of the physical design of a chip matches the logical design of the chip represented by a schematic and to verify that a design of an IC chip conforms to certain manufacturing tolerances that are required in fabricating the chip. Parasitic extraction generates an equivalent model of the integrated circuit, modeling and extracting the parasitic resistance, inductance and capacitance of the chip. These tools exist in one or more areas commonly referred to as electronic design automation (EDA), electronic computer aided design (ECAD), and technology computer aided design (TCAD). A single EDA platform can offer software modules for integrated circuit layout design, behavioral simulation, and functional analysis and verification.
Several tools and methodologies have been developed based on equivalent circuit extraction to allow for fast and accurate modeling of the interconnection network belonging to a semiconductor layout. In such methodologies, the interconnect structures of the integrated circuit are divided into smaller sections, and each section is modeled by an equivalent circuit that models its electromagnetic behavior, including electrical behavior, along with any parasitic couplings to the substrate or other nearby structures. LPE (layout parasitic extraction) methodologies can be fast and efficient, and their output is usually a circuit netlist comprising R (resistor) and C (capacitor) lumped elements. Some methods are also capable of separately producing L (inductance) and K (mutual inductance) elements which, besides resistor and capacitor elements, are oftentimes required to accurately model the electromagnetic (EM) behavior of an IC at higher frequencies.
A netlist provides a description of the elements connected between the nodes of a circuit, and can contain a very large amount of information that may consequently be difficult to process, analyze and manipulate. Model-order reduction is an important technique to accelerate the simulation of netlists with large size (>1M of elements) and many ports (>10). Among many model-order reduction algorithms, those based on projection methods provide both increased accuracy and optimal performance. The majority of model-order reduction algorithms that fall in this category commonly rely on the Krylov subspace projection method, as implemented in PRIMA method (see Odabasioglu, M. Celik, and L. T. Pileggi, “PRIMA: passive reduced-order interconnect macromodeling algorithm”, IEEE Trans. on CAD of Integrated Circuits and Systems, 17(8):645-654, 1998) using the Arnoldi process and the input-output structure-preserving model order reduction methodology. (See Yang, X. Zeng, Y. Su, and D. Zhou, “RLC equivalent circuit synthesis method for structure-preserved reduced order model of interconnects in VLSI”, Communication in Computational Physics, 3(2):376-396, 2008).
The input-output structure-preserving model-order reduction methodology as described in Yang can be considered an extension of the SPRIM method (see R. W. Freund. “Sprim: structure-preserving reduced-order interconnect macromodeling,” Computer Aided Design, 2004, ICCAD-2004. IEEE/ACM International Conference on, pages 80-87, November 2004. See also U.S. Pat. No. 7,228,259 to Freund).
To understand model-order reduction, a review of the algorithms underlying circuit representation in a netlist is useful. These algorithms rely on modified nodal analysis (MNA) formulations underpinned by Kirchhoff's current and voltage laws, which can be expressed through a directional graph. The edges of the graph correspond to the circuit elements, while the nodes of the graph correspond to the nodes of the circuit, denoting the interconnections of the circuit elements. An arbitrary direction is assigned to graph edges, so that one can distinguish between the source and destination nodes. The directional graph can be described by its incidence matrix A, which is formed as follows: Each row of A corresponds to a graph edge and, therefore, to a circuit element. Each column of A corresponds to a graph or circuit node. Each edge e is formed from an ordered pair of nodes n1 and n2, where the direction of e is from n1 to n2. The column corresponding to the ground node of the circuit is deleted in order to remove redundancy. For a row which is associated with the edge e, the column position which corresponds to the source node n1 contains the entry “1”, while the column position which corresponds to the destination n2 contains the entry “−1”. For all the other cases the entries are “0”.
Kirchhoff s current and voltage laws can be expressed using matrix A:ATib=0  Eq. 1Avn=vb  Eq. 2
where ib is the vector of the currents through the circuit elements, vb is the vector of the voltages across the circuit elements, and vb is the vector of the voltages at the nodes of the circuit (the non-datum voltages). For the ground node the voltage is assumed zero.
In the most general case of analyzing RLCk circuits, we assume that the circuit is excited by voltage and current sources. In this case, the matrix A and the vectors ib and vb can be partitioned according to circuit-element types:
                    A        =                                            (                                                                                          A                      v                                                                                                                                  A                      i                                                                                                                                  A                      g                                                                                                                                  A                      c                                                                                                                                  A                      l                                                                                  )                        ⁢                                                  ⁢                          i              b                                =                                                    (                                                                                                    i                        v                                                                                                                                                i                        i                                                                                                                                                i                        g                                                                                                                                                i                        c                                                                                                                                                i                        l                                                                                            )                            ⁢                                                          ⁢                              v                b                                      =                          (                                                                                          v                      v                                                                                                                                  v                      i                                                                                                                                  v                      g                                                                                                                                  v                      c                                                                                                                                  v                      i                                                                                  )                                                          Eq        .                                  ⁢        3            where the subscripts g, c, l refer to branches with resistors, capacitors and inductors respectively and the subscripts v, i denote the voltage and current sources of the network respectively.The physical behavior of the circuit elements is described by the branch constitutive (BCR) relations:
                                          i            g                    =                      gv            g                          ⁢                                  ⁢                              i            c                    =                      c            ⁢                          ∂              dt                        ⁢                          v              c                                      ⁢                                  ⁢                              v            i                    =                      l            ⁢                          ∂              dt                        ⁢                          i              l                                                          Eq        .                                  ⁢        4            Where:                g and c are diagonal matrices, whose entries correspond to the conductance and capacitance values of each element. These values are positive for any physical circuit, and consequently, both matrices g and c are symmetric positive definite.        l is the inductance matrix, which is also symmetric positive definite. If mutual inductances are included, then l is a full matrix; otherwise it is a diagonal matrix.The BCRs for the independent voltage and current sources of the network simply state that vv and ii are given functions that can be chosen as inputs to the network, whereas vi and iv are unknown output functions that need to be determined as part of the problem of solving the system of equations describing the given RLC network.        
A Modified Nodal Analysis (MNA) formulation according to C.-W. HO, A. E. Ruehli, P. A. Brennan, “The Modified Nodal Approach to Network Analysis”, IEEE Transactions on Circuits and Systems, Vol. 1X-22, No. 6, June 1975, can be extracted by combining equations 1, 2 and 4, eliminating the current unknowns. MNA equations provide a system representation of an RLCk netlist, as a set of equations that form the time-domain state space representation. For a N-port network, this state space relates the port voltages and currents (vv and ii) via the state-space vector x, i.e. the node voltages (vn) and the branch currents for voltage sources (iv) and inductors (il):C{dot over (x)}+Gx=Bu y=BTx  Eq. 5The vectors u,y are called input and output vector respectively.
            Where                                                      x        =                                            [                                                                                          v                      n                                                                                                                                  i                      l                                                                                                                                  i                      v                                                                                  ]                        ⁢                                                  ⁢            u                    =                                                    [                                                                                                    -                                                  i                          i                                                                                                                                                                        v                        v                                                                                            ]                            ⁢                                                          ⁢              y                        =                          [                                                                                          v                      i                                                                                                                                  i                      v                                                                                  ]                                                          Eq        .                                  ⁢        6                                          C          =                                                    [                                                                            Q                                                              0                                                                                                  0                                                              l                                                                      ]                            ⁢                                                          ⁢              G                        =                                                            [                                                                                    N                                                                                              A                          l                          T                                                                                                                                                              -                                                      A                            i                                                                                                                      0                                                                              ]                                ⁢                                                                  ⁢                B                            =                              [                                                                                                    A                        i                                                                                                                        0                                                                      ]                                                    ⁢                                  ⁢                              Q            =                                          A                c                T                            ⁢                              cA                c                                              ,                                          ⁢                      N            =                                          A                g                T                            ⁢                                                          ⁢              g              ⁢                                                          ⁢                              A                g                                                    ⁢                                  ⁢                  Where          ⁢                      :                          ⁢                                  ⁢                              B            ∈                          R                                                (                                                            N                      V                                        +                                          N                      l                                        +                    K                                    )                                ⁢                x                ⁢                                                                  ⁢                K                                              ,                                          ⁢                                    A              i                        ∈                          R                              K                ⁢                                                                  ⁢                x                ⁢                                                                  ⁢                K                                              ,                                          ⁢                      N            ∈                          R                                                (                                                            N                      V                                        +                    K                                    )                                ⁢                                  x                  ⁡                                      (                                                                  N                        V                                            +                      K                                        )                                                                                ,                                          ⁢                      Q            ∈                          R                                                (                                                            N                      V                                        +                    K                                    )                                ⁢                                  x                  ⁡                                      (                                                                  N                        V                                            +                      K                                        )                                                                                ,                                          ⁢                      l            ∈                          R                                                N                  l                                ⁢                x                ⁢                                                                  ⁢                                  N                  l                                                              ,                                          ⁢                                    A              l              T                        ∈                          R                                                (                                                            N                      V                                        +                    K                                    )                                ⁢                x                ⁢                                                                  ⁢                                  N                  l                                                                                        Eq        .                                  ⁢        7            
and Nv is the number of internal nodes, Nl is the number of inductors and K the number of ports.
PRIMA Algorithm
The Passive Reduced-Order Interconnect Macromodeling Algorithm (PRIMA) Odabasioglu, M. Celik, and L. T. Pileggi. “PRIMA: passive reduced-order interconnect macromodeling algorithm”. IEEE Trans. on CAD of Integrated Circuits and Systems, 17(8):645-654, 1998, is based on the block Arnoldi algorithm, but employs congruence transformations to project a large system of equations onto a smaller subspace, so that passivity is preserved during reduction. PRIMA uses the Arnoldi iteration as a numerically stable method of generating the Krylov subspace. The transformation matrix matches the first n=(q/K) moments for all k ports, where q is the number of nodes. Since the PRIMA reduced order models are generated via projection onto Krylov subspaces, they satisfy the moment-matching property and are guaranteed to be passive. Given the number of nodes q in the reduced netlist and the number of ports K, n=q/K+1 iterations of the block Arnoldi algorithm are performed to derive the projection matrix V (the extra step is required in case that (q/K) is not an integer).
The PRIMA algorithm is performed as described in Table 1:
TABLE 1The PRIMA algorithmR = (G + s0C)−1B,QR decomposition on R − (V0, T) = qr(R)A = −(G + s0C)−1CV0for k = 1,2,...,n Set Vk(0) = AVk−1 for j = 1,...,k  Vk(j) − Vk(j−1) − Vk−jVk−jTVk(j−1) end  Vk = orth(Vk(k))endset V = [V0V1V2 ... Vn],
In the original deployment of the algorithm, s0 was supposed to be equal to zero. However experimental results indicated that setting s0=0 leads usually to a close to singular matrix and instability of numerical calculations. Instead of this, an initial s0=2πf is selected by generating a relatively low frequency expansion point, in comparison to the reference bandwidth upper limit and taking care to avoid singularity of the matrix to be inversed.
Structure & I/O Preservation
The matrices G, C and B present certain block structures, which reflect the states of an RCLk circuit. For a given expansion point s0, the reduced-order model generated via projection does not preserve these block structures of the data matrices. In fact, the transformation matrix will be a dense matrix, and then the data matrices of the reduced-order model will also be dense matrices. As a result, synthesizing the system described by the reduced order model, as an actual RLCK electronic circuit, will not be feasible.
A first improvement was performed using the SPRIM approach (R. W. Freund. “Sprim: structure-preserving reduced-order interconnect macromodeling.” Computer Aided Design, 2004. ICCAD-2004. IEEE/ACM International Conference on, pages 80-87, November 2004). In contrast to PRIMA, the SPRIM algorithm does not use the matrix V directly for the projection of the original data matrices. Instead, SPRIM utilizes a modified version of the specific matrix:
                              V          SPRIM                =                  [                                                                      V                  1                                                            0                                                                    0                                                              V                  2                                                              ]                                    Eq        .                                  ⁢        8            
Matrices V1εR(Nv+K)×n and V2εRNL×n correspond to the block sizes of G and C respectively. Applying VSPRIM as a projection matrix, a reduced order model is obtained that matches twice as many moments as PRIMA, while the block structure of Eq. 7 is preserved.
Further improvement is introduced by the IOPOR technique (F. Yang, X. Zeng, Y. Su, and D. Zhou, “RLC equivalent circuit synthesis method for structure-preserved reduced order model of interconnects in VLSI”, Communication in Computational Physics, 3(2):376-396, 2008) which, in addition to preserving the block structure of the transformation matrices, also preserves the structures of input and output incidence matrices of the system. Starting from the PRIMA projection matrix, the new projection matrix is formed as follows:
                              V          IOPOR                =                  [                                                                      I                                      k                    ×                    k                                                                              0                                            0                                                                    0                                                              V                  1                                                            0                                                                    0                                            0                                                              V                  2                                                              ]                                    Eq        .                                  ⁢        9            Where:                Ik×k: Identity Matrix        V1: Nv×n matrix        V2: Nl×n matrixIf the initial state equations are arranged in such a way that terminal nodes occupy the first k rows of state equation matrices, then the application of the new projection matrix on the initial system preserves both the block structure of equations and the structure of input output incidence matrices. To achieve the final reduced circuit, state equations are reformulated in a second-order form in the frequency-domain. By eliminating in Eq. 6, we obtain the second order system:        
                                          (                          sQ              +              N              +                              F                s                                      )                    ⁢          x                =                              A            i                    ⁢          u                                    Eq        .                                  ⁢        10            where all the system matrices Q, N and F are symmetric and positive semi-definite, F=AlTl−1Al is the susceptance matrix, and
      A    i    =            (                                                  I                              K                ×                K                                                                                        0                                                N                  v                                ×                K                                                        )        .  Setting
  W  =      (                                        I                          k              ×              k                                                0                                      0                                      V            1                                )  in Eq. 9, we obtain the transformed second order system as:
            (                        s          ⁢                                          ⁢                      Q            ~                          +                  N          ~                +                              F            ~                    s                    )        ⁢          x      ~        =            A      i        ⁢    u                  Where:{tilde over (Q)}=WTQW, Ñ=WTNW, Ãi=WTAi {tilde over (l)}=V2TlV2, Ãl=WTAlV2, {tilde over (F)}=ÃTl{tilde over (l)}−1Ãl  Eq. 11        
The second-order description of the reduced system (Eq.12) can be viewed as the nodal equation of a circuit with q nodes, which describes the Kirchhoff current law, satisfied in each node of the circuit.
                                          (                                          s                ⁢                                                                  ⁢                                  Q                  ~                                            +                              N                ~                            +                                                F                  ~                                s                                      )                    ⁢                      x            ~                          =                                            A              ~                        i                    ⁢          u                                    Eq        .                                  ⁢        12            
As explained above, to efficiently integrate the reduced matrices into a simulation methodology flow, the reduced model must be represented in a netlist suitable to be used from any simulation software (Spice, Spectre, etc.). However, after unstamping, a synthesized netlist may include non-physical elements, such as negative RLC (See Yang, X. Zeng, Y. Su, and D. Zhou, “RLC equivalent circuit synthesis method for structure-preserved reduced order model of interconnects in VLSI”, Communication in Computational Physics, 3(2):376-396, 2008)), or a large number of controlled sources (see Neumayer, R., Haslinger, F., Stelzer, A., Weiger, R., “On the synthesis of equivalent-circuit models for multiports characterized by frequency-dependent parameters”, IEEE Transactions on Microwave Theory and Techniques, Volume 50, Issue 12, published 2002, Previously presented. 2789-2796). In such a case, the netlist is of limited use since many simulators cannot handle negative value components. Furthermore, the existence of negative elements (for simulators that accept negative values) or controlled sources result in netlists that are not noise compatible.
In Fernandes Villena, J. “Positive realization of reduced RLCM nets”, 19th International Conference on VLSI and System-On-Chip (VLSI-SoC), 2011 IEEE/IFIP, a methodology is presented based on a specific manipulation of the reduced matrices, to ensure that all elements in the equivalent RLC netlist are guaranteed to be positive. A side effect is that the matrix which relates the ports to the internal nodes of the reduced netlist is not preserved. As a result, in order to keep the port connectivity with the internal nodes, a set of current and voltage controlled sources are included, increasing the netlist size especially for netlists with large numbers of ports.
There is therefore a need to improve the unstamping procedure, to realize a positive netlist (RLCk) with reduced or no controlled sources.